import heapq

n, m, s, d = map(int, input().split())
table = [[-1 for i in range(n)]] * n
people = list(map(int, input().split()))
for i in range(m):
    ss, dd, ll = map(int, input().split())
    table[ss][dd] = ll


def f(graph, start):
    n = len(graph)
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]
    visited = set()

    while heap:
        (d, u) = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))

    return dist
